﻿package com.flashshe.ds.list
{
	

	public class CircularLinkedList extends AbstractList
	{
		private var tail:SinglyLinkedListElement;		
		private var count:int = 0;
		
		
		public function CircularLinkedList()
		{
			super();
		}
		
		public override function get size():int
		{
			return count;
		}
		
		public override function clear():void
		{
			tail = null;
			count = 0;
		}				
		
		public override function add(v:Object):void
		{									
			//空列表
			if (tail == null)
			{
				tail = new SinglyLinkedListElement(v);
				tail.nextElement = tail;
			}
			else
			{
				var temp:SinglyLinkedListElement = new SinglyLinkedListElement(v, tail.nextElement);
				tail.nextElement = temp;
				tail = temp;				
			}
			
			count += 1;
		}
		
		public override function addAt(index:uint, v:Object):void
		{			
			if (index > size)
			{
				throw new RangeError("提供的索引超出了范围");
			}			
			
			if (tail == null)
			{
				add(v);
				return;
			}
						
			
			// 列表中至少有一个元素			
			
			//插入列表头部
			if (0 == index)
			{
				var temp:SinglyLinkedListElement = new SinglyLinkedListElement(v, tail.nextElement);
				tail.nextElement = temp;				
				count += 1;
				return;
			}
			
			if (index == size)
			{
				add(v);
				return;
			}
			
			// 列表中至少有两个元素并且不会插入头部
			var i:int = 0;			
			var finger:SinglyLinkedListElement = tail.nextElement;
			var pre:SinglyLinkedListElement = null;
			
			while(finger.nextElement)
			{
				pre = finger;
				finger = finger.nextElement;
				i += 1;
				if (i == index)
				{
					break;
				}				
			}
			
			pre.nextElement = new SinglyLinkedListElement(v, finger);
									
			count += 1;
		}
				
		public override function getValueAt(index:uint):Object
		{
			if (index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}
			
			var finger:SinglyLinkedListElement = tail.nextElement;
			var i:int = 0;
			
			do 
			{
				if (i == index)
				{					
					return finger.value;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i <= index);

			return null;
		}
		
		public override function getLast():Object
		{
			return tail.value;
		}
		
		public override function removeAt(index:uint):Object
		{
			if (index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}	
			
			var i:int = -1;			
			var finger:SinglyLinkedListElement = tail;
			var pre:SinglyLinkedListElement = null;
			
			while(finger.nextElement)
			{
				pre = finger;
				finger = finger.nextElement;
				i += 1;
				if (i == index)
				{
					break;
				}				
			}
			
			pre.nextElement = finger.nextElement;			
			count -= 1;
			
			return finger.value;
		}
		
		public override function remove():Object
		{						
			return removeAt(size-1);
		}
		
		public override function setValueAt(index:uint, v:Object):Object
		{
			if (index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}
			
			var i:int = 0;			
			var finger:SinglyLinkedListElement = tail.nextElement;
			
			do
			{
				if (i == index)
				{					
					var result:Object = finger.value;
					finger.value = v;
					return result;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i < count);			
			
			return null;
		}							
				
		public override function indexOf(v:Object, startIndex:uint=0):int
		{
			if (count == 0 || startIndex >= count)
			{
				return -1;
			}
			
			var i:int = 0;	
			// tail.nextElement 指向列表头
			var finger:SinglyLinkedListElement = tail.nextElement;
			
			do
			{
				if (finger.value == v && i >= startIndex)
				{					
					return i;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i < count);
			
			return -1;
		}
		
		/*public override function iterator():IIterator
		{
			return null;
		}*/
	}
}